//
// Created by liushuai on 2021/2/9.
//

#include "reorderList.h"

//ListNode* mergeOrder(ListNode* head1,ListNode* head2){
//    if(head1&&head2){
//        ListNode* nextNode = head1->next;
//        head1->next = mergeOrder(head2,nextNode);
//    }
//    if(head1&&!head2){
//        return head1;
//    }
//    if(!head1&&head2){
//        return head2;
//    }
//    return head1;
//}
void reorderList(ListNode *head){
    ListNode* fastNode = head;
    ListNode* slowNode = head;
    ListNode* preNode = nullptr;
    while (fastNode&&fastNode->next){
        preNode = slowNode;
        fastNode = fastNode->next->next;
        slowNode = slowNode->next;
    }

    ListNode* head1 = head;
    ListNode* head2 = reverseLinklist(slowNode);
    while(head1&&head2){
        ListNode* nextNode1 = head1->next;
        ListNode* nextNode2 = head2->next;

        head1->next = head2;
        head1 = nextNode1;
        head2->next = head1;
        head2 = nextNode2;
    }

}